/*
题目: 字典序的第K小数字
给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。

https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/
 */
public class FindKthNumber {
    public int findKthNumber(int n, int k) {
        long cur = 1;

        // 当 k 减到 1 的时候, 就是 第 k 小的元素
        while (k > 1) {
            long steps = getSteps(cur, n); // 获取当前结点 共有多少个子结点, 包括 本身
            if (k <= steps) {  // 如果 结点数量 < k, 说明 目标 在这个子树中, 直接进入 下一层
                k --;
                cur *= 10;
            } else { // k > steps, 如果目标不在这个子树中
                k -= steps;
                cur ++;
            }
        }

        return (int) cur;
    }

    private long getSteps(long cur, int n) {
        long steps = 0;
        long front = cur;
        long last = cur;
        while (front <= n) {
            // while 的每一层循环 都是记录 这个结点的当前层子结点的个数
            steps += Math.min(n, last) - front + 1;// 获取 包括自身 的子节点总数, min 防止溢出
            front = front * 10;
            last = last * 10 + 9;
        }
        return steps;
    }
}
